#include <stdio.h>
#include <stdlib.h>
// 结点的定义
typedef int ElementType;
typedef struct ListNode {
    ElementType data;
    struct ListNode *next;
}ListNode;

// 创建结点
ListNode* createNode(ElementType x) {
    ListNode *newNode = (ListNode *)malloc(sizeof(ListNode));
    if (newNode == NULL) {
        printf("内存空间分配失败\n");
        exit(1);
    }
    newNode->data = x;
    newNode->next = NULL;
}

// 查找pos前一个结点的指针
ListNode* findListNodeByPos(ListNode *head, int pos) {
    if(head == NULL) {
        printf("参数有误\n");
        return NULL;
    }
    ListNode *preNode = head;
    for(int i = 0; i < pos - 1; i++) {
        preNode = preNode->next;
    }
    return preNode;
}

// 插入结点
void insert(ListNode *head, int pos, ElementType x) {
    if (pos < 1) {
        printf("插入位置不合法\n");
        return;
    }
    ListNode *newNode = createNode(x);
    if (pos == 1) {
        newNode->next = head->next;
        head->next = newNode;
    } else {
        ListNode *preNode = findListNodeByPos(head, pos);
        newNode->next = preNode->next;
        preNode->next = newNode;
    }
}

// 打印链表
void printList(ListNode *head) {
    if(head == NULL) {
        printf("参数有误\n");
        return;
    }
    while (head->next != NULL) {
        printf("%d ", head->next->data);
        head = head->next;
    }
    printf("\n");
}

ListNode* delete(ListNode *head, int pos){
    if(head == NULL) {
        printf("参数有误\n");
        return NULL;
    }
    ListNode *preNode = findListNodeByPos(head, pos);
    ListNode *delNode = preNode->next;
    preNode->next = delNode->next;
    return delNode;
}

int main(void) {
    ListNode *head = (ListNode *)malloc(sizeof(ListNode));
    head->next = NULL;
    // 插入
    insert(head, 1, 1);
    insert(head, 2, 2);
    insert(head, 3, 3);
    printList(head);
    // 删除
    delete(head, 2);
    delete(head, 2);
    printList(head);

    return 0;
}
